package com.dhu.graph.digraph;

import com.dhu.graph.basic.GraphImpls.DiGraph;
import com.dhu.graph.utils.ArrayQueue;

import java.util.Stack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-03
 * @ Description：判断有向图是否存在环，不找出所有的环，只是检测出一个环并把这个环记录下来即可
 * @ Modified By：
 * @ Version:
 */
public class DirectedCycle {

    private boolean[] marked;
    private boolean[] onStack;  // 是否在递归调用的栈上
    private Integer[] pathsTo;
    private int count;
    private boolean recordCycles; // 是否找出所有的环，并记录所有的环
    private ArrayQueue<Stack> cycles;

    public DirectedCycle(DiGraph G, boolean recordCycles){
        this.marked = new boolean[G.V()];
        this.onStack = new boolean[G.V()];
        pathsTo = new Integer[G.V()];
        this.recordCycles = recordCycles;
        this.cycles = new ArrayQueue<Stack>();
        for (int i = 0; i < G.V(); i++) {
            dfs(G, i);
        }
    }
    public DirectedCycle(DiGraph G){
        this(G, false);
    }

    /**
     * 该算法中维持了onStack变量，其意义就是标明被标记了的点(marked = true) 是在本次递归调用体系中被标记了的点，因为在构造器中
     * 需要遍历dfs每一个顶点，在先前的dfs中，某些顶点可能已经被标记了，访问到marked = true的顶点，并不意味着这是一个环，也许只是一条曲线
     * 只是在构造器中别的dfs调用中已经被标记，只有遇到marked和onStack同时为true,才表用这是同一次dfs中被标记，遇到marked为true
     * 由于是单向的路径，所以证明遇到了环。
     * @param G
     * @param s
     */
    private void dfs(DiGraph G, int s){
        marked[s] = true;
        onStack[s] = true;
        for (Integer w : G.adj(s)) {
            if(hasCycle() && !recordCycles) return;
            else if(!marked[w]){
                pathsTo[w] = s;
                dfs(G, w);
            }
            else if (onStack[w]){
                Stack<Integer> aCycle = new Stack<Integer>();
                for (int x = s; x != w; x = pathsTo[x]){
                    aCycle.push(x);
                }
                aCycle.push(w);
                aCycle.push(s);
                count ++;
                cycles.enqueue(aCycle);
//                return;  // 在这里返回会报空指针异常,虽然在这一次递归中它反回了，并记录了cycle,
                // 但是在构造器中要dfs每一个顶点，在这里return,当前顶点onStack就不执行赋值为false,
                // 所以在构造器中的下次调用会不出现本还未形成环，却条件满足环的现象，从而在再次执行cycle.push时，
                //pathsTo是回不到w的，从而会产生空指针异常。
            }
        }
        onStack[s] = false;
    }
    public boolean hasCycle(){
        return !this.cycles.isEmpty();
    }
    public int cycleCount(){
        return this.count;
    }

    public Iterable cycles(){
        return this.cycles;
    }
}
